package Leetcode.树;

import java.util.*;

/**
 * 给你一棵二叉树的根节点 root 和一个正整数 k 。
 *
 * 树中的 层和 是指 同一层 上节点值的总和。
 *
 * 返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
 *
 * 注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
 *
 * 树中的节点数为 n
 * 2 <= n <= 105
 * 1 <= Node.val <= 106
 * 1 <= k <= n
 */
public class 二叉树中的第K大层和 {
    /**
     * 1.先求各层节点的层和（层序遍历）   组成一个list  然后排序
     * 2.层和求第k大的数
     * @param root
     * @param k
     * @return
     */
    public static long kthLargestLevelSum(TreeNode root, int k) {
        List<Long> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);//放头节点
        while (!que.isEmpty()) {
            long sum = 0;
            List<TreeNode> temp = new ArrayList<TreeNode>(que);
            que.clear();//移除所有元素
            for (TreeNode treeNode : temp) {
                //将每一层添加到que中，做层序遍历
                sum += treeNode.val;
                if (treeNode.left != null) {
                    que.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    que.offer(treeNode.right);
                }
            }
            res.add(sum);
        }
        if (res.size() < k) {
            return -1;
        }
        Collections.sort(res);
        return res.get(res.size() - k);
    }

    public static void main(String[] args) {
        Integer[] a = {5, 8, 9, 2, 1, 3, 7, 4, 6};
        TreeNode t = TreeNode.arrayToTree(a);
        long l = kthLargestLevelSum(t, 2);
        System.out.println(l);
    }
}
